package leetcode_question;


import tree.Trie;

import java.util.TreeMap;

/**
 * LeetCode 211
 */
public class WordDictionary {

    private class Node{

        public boolean isWord;
        public TreeMap< Character , Node > next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }

        public Node(){
            this(false);
        }
    }

    private Node root;

    public WordDictionary(){
        root = new Node();
    }

    public void addWord(String word){
        addWord(root,word,0);
    }

    private void addWord(Node node , String word , int index){
        if( index == word.length() ){
            if(node.isWord == false){
                node.isWord = true;
            }
            return;
        }

        char c = word.charAt(index);
        if(node.next.get(c) == null){
            node.next.put(c , new Node());
        }

        addWord(node.next.get(c) , word , index + 1);
    }

    public boolean search(String word){

        return match(root,word,0);

    }

    // .可以匹配任意字符
    private boolean match(Node node , String word, int index){

        if( index == word.length() ){
            return node.isWord;
        }

        char c = word.charAt(index);
        if( c != '.'){
            if(node.next.get(c)  == null){
                return false;
            }
            return match(node.next.get(c), word , index + 1);
        }else {
            // 因为 . 能匹配任意字符，所以需要将所有node.next 下的所有字符都匹配一次
            for (char nextChar : node.next.keySet()){
                if( match(node.next.get(nextChar) , word , index + 1) ){
                    return true;
                }
            }
            return false;
        }
    }

}
